Hi, everyone.
Welcome back to the Heterogenious Parallel Programming class.
We are at lecture 1.8, Kernel-Based Parallel Programming,
and we will be discussing basic matrix-matrix multiplication.
The objective for this lecture is to prepare
you for the lab assignment of matrix-matrix multiplication.
And we will first review the computation for matrix multiplication.
And we will also discuss how we can do data
block and thread index to data index mapping for this particular computation.
And then we will introduce loop control flow in kernels.
Matrix multiplication is a fairly frequently
used computation in engineering and science applications and the
computation is fairly simple. We have two input matrices A and B.
And then we will generate a product matrix C.
The each C element is generated as a product of a row of A and
a column of B. So we in this particular picture,
we show that a C element has a coordinate row
at Col. And so we would use a row in
A with the index Row, and then we will have a column
of B with the index Col. And we will take the
row and the column to take, to do a vector.product to
generate the value of the C element. In
all the discussions that we have today, we will assume that we would be doing
a we will have A matrix which is of dimension m times n.
And B matrix will be of dimension n
times k.
And then we will generate a C matrix n times k.
So the n part is going to the number of elements in
a row and the number of elements in a column, which is n of B.
Which is represented in variable n here, must
match, because we're doing a .product so we must
have the same number of elements of A and the
same number of elements of B in that in that .product.
So we are going to use these variables
consistently in all the examples in this lecture.
So, here we show a simple sequential C code for matrix multiplication.
And the C code will have have two levels of loops.
And the loop these two levels of loops systematically go
through all the C elements in all the row positions and row,
all the column positions. And for every C element
that it visits it would generate a top product of, of the
A, corresponding A row and B column for that C element.
So here is the C code for generating each C element.
We'll first initialize the c element to 0, and then we will
go and systematically visit all the elements in the row of A and
column of B.
When we visit the row of A, we will
first need to reached the beginning location of that row.
And the beginning location is is can be found by multiplying
variable row, by the number of elements in each row, which is m.
So, row times n moves us into the beginning location of the row
in the linear row major layout of A. And then we do the same thing with B.
In B's case, the beginning location of the column is actually in row 0.
So it's simply, a we can simply use Col to move the
you know the, to move the the, the index into the beginning element of B.
Now, with for every iteration of the I loop, we will need to be able
to calculate the corresponding element within the row and column.
So for A it's very simple.
We all the elements in the in the same row are going to be in adjacent locations.
So all we have to do is to just add i to the beginning index, and that
will give us the the element, in the property element for that iteration.
For B it's a little bit more complex because in row major layout
all the elements in the column are going to be in strided locations.
So we need to multiply i by the number of elements in each row, which is k
for, for B and then we, we add that to the beginning location.
So these two memory accesses give us the appropriate elements
of A and B in each iteration. And then we would do the multiplication.
We accumulate the result into sum. And this once we finish
the for loop, we have the total value for the C element.
So now we can write the C element value into the into the appropriate
C location and this is the location at row and column.
So we again we will just calculate the linearized address by
multiplying row with k, and then add column to the index.
So this gives us the complete C sequential code for matrix multiplication.
Notice that this particular calculation is a very
simple and very basic form.
And since matrix multiplication is a very important computation, there are
actually lots and lots of optimized ways of doing sequential computation.
We will come back to this point later on.
So here we will begin to design a kernel
function in CUDA to perform matrix multiplication in parallel.
So we're going to use a very small example to to
give you the intuition behind the design of the kernel function.
So here we're going to assume that we
are going to be using a two dimensional square,
square block to organize the threads to calculate C.
And that is each thread block is going to have
equal number of threads in both X and Y dimension.
And obviously, this is a simplifying assumption, that
you can you can definitely use a rectangular
block organization, but here we use a, a
square organization, just to keep the, the slide simple.
And so, assuming that we, we have a square organization,
we will just assume that we have a compile time defined constant of tile width.
And this tile width is going to give us the
number of threads in each dimension of the thread block.
And we we, we have a simple example here of C to calculate
a C matrix of 4 times 3 for a 4 by 3 matrix for C.
So in this case, m equal to 4, and K equal to 3.
We also will further assume that n is 4 for both A and B
and which is not visible in this light, but will become useful later on.
So for this very simple small example we
have four elements in the Y dimension and three elements in the X dimension of C.
And we need to make sure that we generate
enough thread blocks to calculate all the C elements.
If we assume that the tile width is 2 for this simple example then we can, we will
go through the same ceiling function calculation and we
would that we use before in the picture kernel.
Then we will,
we will conclude that we need to have two thread
blocks in the Y dimension as well as two thread
blocks in the X dimension to be able to to
cover the generation of, calculation of all the C elements.
So this give us the simple example that we are going to working with.
And in every thread block, we are going to have
two threads in the X dimension and two, two threads
in the Y dimension so that these threads are going to be accessing the C
elements that are located in the pile that this thread block is responsible for.
So now we are ready to to discuss the host code for evoking the matrix
multiplication kernel and we assume that we have the, the matrix
dimension variables m, n and k available in the host code.
So we will be generating in we will be using the ceiling function expression
based on k and n to generate enough thread blocks for covering all the C elements.
So this is just you know, very similar to what we used in the picture kernel.
And for each thread block we are going to declare that we are going to
have thread width and thread width number of threads in the X and Y dimension.
And we will because Z dimension is not used,
we're going to be just using 1 for that dimension.
So we will be launching the kernel
with the grid dimension and block dimension that
we set up in the host code, and then we will
pass m, n, k and the pointers to A, B and C.
Just another reminder A matrix is going to be m times n,
the B matrix is going to be n times k, and C matrix is going to be m times k.
Here we show the matrix multiplication kernel.
And we, at the beginning, every thread is going to determine the
row and column index of the C element that it's it's calculating.
And then they will all proceed to test whether the
row index and column index are within the valid range.
If these indices are within the valid range, then we will
do, go through that for loop to access the elements of the row
of A and the elements of the column of B to produce the inner product.
So this is pretty much the same as the sequential code.
And after the for loop, we, you know, we have the C element value.
So we will, we write a C element value into the global memory, and
the calculation is exactly the same as C. So this is the reason why we took
the time to discuss the row major layout and the linearization of variables.
You know, keep in mind that in, in CUDA because A, B and C
are all going to be dynamically allocated with cudaMalloc.
So that's why we need to you know, do the linearization in
the of these indices when we read from A and B and right into C.
Now we are ready to to review just a
little bit more dynamic execution behavior of the kernel.
So as we mentioned there will be four thread blocks, executing this
kernel for our small 4 by 3 C example. So we
are going here we show the work that the threadblok 0,0 is
going to be doing. So you know what, for threadbox 0,0
the block index at the x and y dimensions are both 0.
So this means that when we calculate the row index and
column index the these values are solely going to be determined
by the thread index in the x and y dimension.
So here we show that that row and column
indices will be 0 and 1 and for all the four threads.
So let's take a look at the work that thread 0,0 is going to do.
Thread 0,0 is going to have row value of 0 and column value of 0.
So it's going to be accessing
the zeros row of a A and the zeros column of B.
We are showing a horizontal arrow in this direction
here and a vertical arrow down the zeros column
of B to indicate all the memory accesses that
thread 0,0 is going to do in block 0,0.
And then, similarly for thread 1,1, it's going to to, to have a
row value of 1 and column value of 1. So it's going to be accessing
row 1 and column 1 row 1 of A and column 1 of B.
So we're also showing this with the horizontal arrow going through the row
1 and vertical arrows going through column 1 in the in the picture.
So this picture shows the work
that all the four threads in block 0,0 will be doing when executing that kernel.
And in fact your, you, your encouraged to use very small numbers, such
as the ones that we provided here to test your kernel and make
sure that you, you can look at all the numbers and review the
correctness of these numbers before you start
to use your kernel on large matrices.
So just for a little bit more insight we would look at the
work for block 0, 1. In this case the block, the Y dimension
the Y dimension block index is still 0, but the X dimension block index is 1.
So in, in this case the row indexes remain the same because the row index,
indexes are calculated based on the y block index which is 0.
However the x index of the block the x dimension of the block index is now 1.
So we effectively shifted the common value of the threads to
2, 3, compared to block 0, 0. So now we see that all
the threads in this thread block are going to
be processing the upper right corner of the C matrix.
And so if we look at thread 0, 0 in this block, it's going to be still
accessing row 0 of A, but it's going to uh,uh, access accessing column 2 of B.
And then you
will generate that product and write into C 0, 2.
And the more interesting situa-, comparison is
that for thread 0, 1 and thre-, thre-,
thread 1, 0 and thread 1, 1. For those two threads
the they are actually going to be processing column
3 of C, which is outside the valid range.
So, both of those threads are going to
fail the condition test of the if statement.
So the, those thread these two threads will not be doing
any work or doing any kind of memory access in the kernel.
ex-, exec-, execute in the kernel. So this gives us a, a good illustration
of the runtime behavior, and I'd like to encourage you to finish the analysis
of, of, of this example for block 1,0 and block 1,1, okay?
So, at this point, we have finished the the coverage
of the simple matrix multiplication kernel in CUDA.
And you
are ready for the lab. And what I like to reiterate is that
when you test your kernel you should start with some very small matrices.
Such as the dimension that we had, we shown in this in this, in this example.
You can even start with even smaller, like 2 by 2 matrices, and so
that you can use the kind of data value that you know for sure,
you can just calculate by hand and verify that
your kernel is, is doing all the right things.
And then before you can you, you apply the kernel to much
bigger matrices that, of the data that we pro-,uh, supply for your testing.
So in, at this point you, we are at the end of week one.
So I like to also encourage
you to take the quiz as soon as possible to make
sure that you solidify all your understanding of the week one material.
For those of you who'd like to learn more, I'd
like to encourage you to read the textbook, section 4.3.
Thank you.